package code.oldCode.feishuSpecializedTraining.monotone_stack;

import java.util.*;

public class MyMS {
    // 739. 每日温度
    public int[] dailyTemperatures(int[] temperatures) {
        // 1 <= temperatures.length <= 105
        int len = temperatures.length;
        int[] ans = new int[len];
        Deque<Integer> stack = new LinkedList<>();// ArrayDeque LinkedList 在本题效率差不多，都比Stack快很多！~
        // stack"单调栈"(递增),从右到左遍历数组,维护单调栈,因为找的是隔了几天,即位置,故栈存位置
        // 递增单调栈指push的元素必须比栈顶小,越push越小,越pop越大
        for (int i = len - 1; i >= 0; i--) {
            int nowNum = temperatures[i];
            // 把栈中比现在的值小的(位置)全都pop掉,保持栈是递增的
            while (!stack.isEmpty() && nowNum >= temperatures[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                // 右面有比他大的
                ans[i] = stack.peek() - i;
            }
            stack.push(i);
        }
        return ans;
    }

    // 496. 下一个更大元素 I
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // nums1和nums2中所有整数互不相同,nums1是nums2的子集
        // 单调栈+哈希表

        // 1. 利用单调栈，找到nums2的每个元素的右面的第一个比他大的元素
        Deque<Integer> ms = new LinkedList<>();
        int[] nextBig = new int[nums2.length];
        Arrays.fill(nextBig, -1);
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!ms.isEmpty() && nums2[i] >= ms.peek()) {
                ms.pop();
            }
            if (!ms.isEmpty()) {
                nextBig[i] = ms.peek();
            }
            ms.push(nums2[i]);
        }

        // 2. 利用哈希表，存储元素对应nums1的下标
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        // 3. 遍历nums2，若在哈希表内，则赋答案
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i])) {
                ans[map.get(nums2[i])] = nextBig[i];
            }
        }

        return ans;
    }

    // 503. 下一个更大元素 II
    public int[] nextGreaterElements(int[] nums) {
        // 1 <= nums.length <= 104
        int len = nums.length;
        // 单调栈找右侧下一个更大的元素
        Deque<Integer> ms = new LinkedList<>();
        int[] nextBig = new int[len];
        Arrays.fill(nextBig, -1);
        // 由于是循环数组，尝试先找最大值的位置，再从这个最大值的位置从右向左遍历，该循环循环
        int maxPos = 0;
        int max = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] >= max) {
                maxPos = i;
                max = nums[i];
            }
        }
        int leftNum = len;
        int nowPos = maxPos;
        while (leftNum > 0) {
            while (!ms.isEmpty() && nums[nowPos] >= ms.peek()) {
                ms.pop();
            }
            if (!ms.isEmpty()) {
                nextBig[nowPos] = ms.peek();
            }
            ms.push(nums[nowPos]);
            // 遍历下一个的准备
            nowPos--;
            if (nowPos < 0)
                nowPos = len - 1;
            leftNum--;
        }

        return nextBig;
    }
}
